{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subsets II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subsetsWithDup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子集 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。</p>\n",
    "\n",
    "<p>解集 <strong>不能</strong> 包含重复的子集。返回的解集中，子集可以按 <strong>任意顺序</strong> 排列。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,2]\n",
    "<strong>输出：</strong>[[],[1],[1,2],[1,2,2],[2],[2,2]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>[[],[0]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 10</code></li>\n",
    "\t<li><code>-10 <= nums[i] <= 10</code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subsets-ii](https://leetcode.cn/problems/subsets-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subsets-ii](https://leetcode.cn/problems/subsets-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        nums.sort()\n",
    "        \n",
    "        def getComb(nList, res):\n",
    "            if res not in ans:\n",
    "                ans.append(res)\n",
    "            \n",
    "            for i, v in enumerate(nList):\n",
    "                getComb(nList[i+1:], res + [v])\n",
    "                \n",
    "        getComb(nums, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        ret = []\n",
    "        \n",
    "        def backtrack(nums, ret, add, start):\n",
    "            ret.append(add)\n",
    "            for i in range(start, len(nums)):\n",
    "                if i == start or nums[i] != nums[i - 1]:\n",
    "                    backtrack(nums, ret, add + [nums[i]], i + 1)\n",
    "        \n",
    "        nums.sort()\n",
    "        backtrack(nums, ret, [], 0)\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        ans = [[]]\n",
    "        self.getSubset(nums, ans, 0, [])\n",
    "        return ans\n",
    "        \n",
    "    def getSubset(self, nums, ans, i, cur):\n",
    "        if i == len(nums):\n",
    "            return\n",
    "        # if i > 0 and nums[i] == nums[i-1]:\n",
    "        #     self.getSubset(nums, ans, i+1)\n",
    "        #     return\n",
    "        for j in range(i, len(nums)):\n",
    "            if j > i and nums[j] == nums[j-1]:\n",
    "                continue\n",
    "            cur.append(nums[j])\n",
    "            ans.append(cur.copy())\n",
    "            self.getSubset(nums, ans, j+1, cur)\n",
    "            cur.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        nums.sort()\n",
    "\n",
    "        sub_list_index = [[[i] for i in range(len(nums))]]\n",
    "\n",
    "        for sub_length in range(1, len(nums)):\n",
    "            curLength_sub = []\n",
    "            for j in range(len(sub_list_index[sub_length - 1])):\n",
    "                max_num = sub_list_index[sub_length - 1][j][-1]\n",
    "                for k in range(max_num + 1, len(nums)):\n",
    "                    cur_set = []\n",
    "                    cur_set.extend(sub_list_index[sub_length - 1][j])\n",
    "                    cur_set.extend([k])\n",
    "                    curLength_sub.append(cur_set)\n",
    "            sub_list_index.append(curLength_sub)\n",
    "\n",
    "        sub_list = []\n",
    "        for i in range(len(sub_list_index)):\n",
    "            for j in range(len(sub_list_index[i])):\n",
    "                cur_list = []\n",
    "                for k in range(len(sub_list_index[i][j])):\n",
    "                    cur_list.append(nums[sub_list_index[i][j][k]])\n",
    "                sub_list.append(cur_list)\n",
    "\n",
    "        sub_set = set()\n",
    "        for i in range(len(sub_list)):\n",
    "            # for j in range(len(sub_list_index[i])):\n",
    "            sub_set.add(tuple(sub_list[i]))\n",
    "\n",
    "        sub_list = []\n",
    "        for _ in range(len(sub_set)):\n",
    "            sub_list.append(list(sub_set.pop()))\n",
    "        sub_list.append([])\n",
    "\n",
    "        return sub_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        #print([1,2].sort())\n",
    "        list1=[]\n",
    "        final=[[]]\n",
    "        if nums==[]:return final\n",
    "        for i in nums:\n",
    "            i=[i]\n",
    "            \n",
    "            for j in range(len(final)):\n",
    "                a=final[j].copy()+i.copy()\n",
    "                a.sort()\n",
    "                #print(final[j],i ,a,list1)\n",
    "                if a not in list1:\n",
    "                    final.append(a)\n",
    "                    list1.append(a)\n",
    "                if i not in list1:\n",
    "                    final.append(i)\n",
    "                    list1.append(i)\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        tmp = []\n",
    "        self.dfs(res, tmp, nums, 0)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, res, tmp, nums, start):\n",
    "        tmp.sort()\n",
    "        if tmp not in res:\n",
    "            res.append(tmp)\n",
    "        if start == len(nums):\n",
    "            return\n",
    "        for i in range(start, len(nums)):\n",
    "            self.dfs(res, tmp+[nums[i]], nums, i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            cres=res.copy()\n",
    "            for i in cres:\n",
    "                if (sorted(i+[num])) not in res:\n",
    "                    res.append(sorted(i+[num]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: 'List[int]') -> 'List[List[int]]':\n",
    "        nums.sort()\n",
    "        res=[[]]\n",
    "        for i in range(len(nums)):\n",
    "            res+=[subset+[nums[i]] for subset in res]\n",
    "\n",
    "        # 去重\n",
    "        dic={}\n",
    "        for x in res:\n",
    "            dic[str(x)]=0\n",
    "        result=[]\n",
    "        for i in dic.keys():\n",
    "            result.append(eval(i))# 字符串变list，tuple，表达式，神奇\n",
    "        return result\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def huisu(nums,i,item,res):\n",
    "            if i >= len(nums):\n",
    "                return\n",
    "            item.append(nums[i])\n",
    "            print(i)\n",
    "            a=[]\n",
    "            for j in item:\n",
    "                a += [j]\n",
    "            a.sort()\n",
    "            if a not in res:\n",
    "\n",
    "                res.append(a)\n",
    "            huisu(nums,i+1,item,res)\n",
    "            item.pop(-1)\n",
    "            print('i=',i)\n",
    "            huisu(nums,i+1,item,res)\n",
    "        i=0\n",
    "        item=[]\n",
    "        res=[]\n",
    "        huisu(nums,i,item,res)\n",
    "        res.append([])\n",
    "        res.sort()\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        L = [[]]\n",
    "        L1 = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(len(L)):\n",
    "                L1 = L[j] + [nums[i]]\n",
    "                if L1 in L:\n",
    "                    L1 = []\n",
    "                    continue\n",
    "                else:\n",
    "                    L.append(L1)\n",
    "                    L1 = []\n",
    "        return L"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums = sorted(nums)\n",
    "        cache = [[]]\n",
    "        tmp_val = None\n",
    "        left = -1\n",
    "        for i in nums:\n",
    "            if i != tmp_val:\n",
    "                tmp_val = i\n",
    "                tmp_cache = cache.copy()\n",
    "                cache += [j + [i] for j in cache]\n",
    "            else:\n",
    "                for j, v in enumerate(tmp_cache):\n",
    "                    if v != cache[j]:\n",
    "                        left = j\n",
    "                        break\n",
    "                left = len(tmp_cache) if left == -1 else left\n",
    "                tmp_cache = cache.copy()\n",
    "                cache += [j+[i] for j in cache[left:]]\n",
    "                left = -1\n",
    "        return cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        dic = collections.Counter(nums)\n",
    "        res = [[]]\n",
    "        for i, v in dic.items():\n",
    "            temp = res.copy()\n",
    "            for j in res:\n",
    "                temp.extend(j+[i]*(k+1) for k in range(v))\n",
    "            res = temp\n",
    "            #print(res, i, v)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        if not nums:\n",
    "            return res\n",
    "        \n",
    "        def help_subset(curr, k, idx):\n",
    "            if len(curr) == k:\n",
    "                res.append(curr[:])\n",
    "                return\n",
    "            for i in range(idx, len(nums)):\n",
    "                if len(nums)-i < k-len(curr):\n",
    "                    break\n",
    "                if i > idx and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                curr.append(nums[i])\n",
    "                help_subset(curr, k, i+1)\n",
    "                curr.pop()\n",
    "        \n",
    "        nums.sort()\n",
    "        for k in range(1, len(nums)+1):\n",
    "            help_subset([], k, 0)\n",
    "\n",
    "        return res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)+1):\n",
    "            self.Backtracking(nums, i, 0, [], res)\n",
    "        return res\n",
    "    \n",
    "    def Backtracking(self, nums, length:int, index, cur, res):\n",
    "        if len(cur) == length:\n",
    "            if cur not in res:\n",
    "                res.append(cur[:])\n",
    "                return \n",
    "        for i in range(index, len(nums)):\n",
    "            cur.append(nums[i])\n",
    "            self.Backtracking(nums, length, i+1, cur, res)\n",
    "            cur.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        self.helper(res, nums, 0, [])\n",
    "        return res\n",
    "    \n",
    "    def helper(self, res, nums, index, path):\n",
    "        res.append(path)\n",
    "        for i in range(index, len(nums)):\n",
    "            if i > index and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            self.helper(res, nums, i+1, path+[nums[i]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "\n",
    "    def getChild(self, resChild: List[int], nums: List[int]):\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return\n",
    "        for i in range(n):\n",
    "            if i > 0 and nums[i] == nums[i - 1]:\n",
    "                continue\n",
    "            resChild.append(nums[i])\n",
    "            self.getChild(resChild, nums[i+1:])\n",
    "            Solution.res.append(resChild.copy())\n",
    "            resChild.pop()\n",
    "\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        Solution.res = [[]]\n",
    "        self.getChild([], nums)\n",
    "        return Solution.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dfs(i, nums, subset, subsets):\n",
    "\n",
    "\n",
    "    if i == len(nums):\n",
    "        sort_subset = tuple(sorted(subset))\n",
    "        subsets.add(sort_subset)\n",
    "        return\n",
    "    \n",
    "    subset.append(nums[i])\n",
    "    dfs(i+1, nums, subset, subsets)\n",
    "    subset.pop()\n",
    "    dfs(i+1, nums, subset, subsets)\n",
    "    \n",
    "    return\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        subsets = set()\n",
    "        dfs(0, nums, [], subsets)\n",
    "\n",
    "        return [list(subset) for subset in subsets]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "\n",
    "        def backtrack(i,tmp):\n",
    "            res.append(tmp[:])\n",
    "            for j in range(i,n):\n",
    "                tmp.append(nums[j])\n",
    "                backtrack(j+1,tmp)\n",
    "                tmp.pop()\n",
    "        \n",
    "        backtrack(0,[])\n",
    "        res2 = []\n",
    "        for i in res:\n",
    "            if sorted(i) not in res2:\n",
    "                res2.append(sorted(i))\n",
    "        return res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def dfs(tmp, start):\n",
    "\n",
    "            res.append(tmp)               # 要用 列表的 引用，否者更新 tmp 会改变 res 中元素的值\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "\n",
    "                dfs(tmp + [nums[i]], i+1)\n",
    "\n",
    "        res = []\n",
    "        dfs([], 0)\n",
    "\n",
    "        return [ list(element) for element in set([tuple(sorted(ele)) for ele in res]) ]\n",
    "\n",
    "'''\n",
    "        result = []\n",
    "        nums.sort()\n",
    "\n",
    "        def dfs(tmp, start):\n",
    "\n",
    "            result.append(tmp[:])\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "\n",
    "                if i > start and nums[i] == nums[i-1]:  \n",
    "                    continue\n",
    "\n",
    "                tmp.append(nums[i])\n",
    "                dfs(tmp, i+1)\n",
    "                tmp.pop()\n",
    "\n",
    "        dfs([], 0)\n",
    "\n",
    "        return result\n",
    "\n",
    "\n",
    "[1,2,2,2]\n",
    "\n",
    "[[],[1],[1,2],[1,2,2],[1,2,2,2],[2],[2,2],[2,2,2]]\n",
    "\n",
    "              []              backtrack([], 0)\n",
    "     i=0     i=1       i=2    start = 0, i in [0,1,2]  for i in range(0,3)\n",
    "     [1]     [2]       [2]\n",
    "  [1,2]                       start = 1, i in [1,2]    for i in range(1,3)\n",
    "[1,2,3]                       start = 2, i in [2]      for i in range(2,3)\n",
    "\n",
    "https://leetcode-cn.com/problems/subsets-ii/solution/hui-su-suan-fa-by-powcai-6/\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "# 刚开始我们只有空集一个答案，循环所有可能的数字，每次循环我们对当前答案的每一种情况考虑加入从1到上限次该数字并更新答案即可\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        result, track = [], []\n",
    "        nums.sort()\n",
    "        self.backtrack(result, 0, nums, track)\n",
    "        return result\n",
    "\n",
    "    def backtrack(self, result, start, num, track):\n",
    "        result.append(track[:])\n",
    "        print('此时的结果为',result)\n",
    "        for i in range(start, len(num)):\n",
    "            if i > start and num[i] == num[i-1]:\n",
    "                continue\n",
    "\n",
    "            track.append(num[i])\n",
    "            self.backtrack(result, i+1, num, track)\n",
    "            track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        def bt(res, path, start, nums, last_add):\n",
    "            if start == len(nums):\n",
    "                res.append(path[:])\n",
    "                return \n",
    "            \n",
    "            bt(res, path, start+1, nums, last_add=False)\n",
    "\n",
    "            if not(start > 0 and nums[start] == nums[start-1] and last_add == False):\n",
    "                path.append(nums[start])\n",
    "                bt(res, path, start+1, nums, last_add=True)\n",
    "                path.pop()\n",
    "            \n",
    "        res = []\n",
    "        path = []\n",
    "        start = 0\n",
    "        nums.sort()\n",
    "        bt(res, path, start, nums, last_add=False)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        answer = []\n",
    "        answers = []\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        def backtracking(index):\n",
    "            answers.append(answer[:])\n",
    "            \n",
    "            for i in range(index, len(nums)):\n",
    "                if i > index and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                \n",
    "                answer.append(nums[i])\n",
    "                backtracking(i+1)\n",
    "                answer.pop()\n",
    "            pass\n",
    "        \n",
    "        backtracking(0)\n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res, length, tmp = [], len(nums), []\n",
    "        def traverse(idx: int):\n",
    "            if idx == length:\n",
    "                res.append(tmp.copy())\n",
    "                return\n",
    "\n",
    "            tmp.append(nums[idx])\n",
    "            \n",
    "            traverse(idx + 1)\n",
    "            tmp.pop()\n",
    "            # jump over the duplicate\n",
    "            while idx + 1 < length and nums[idx] == nums[idx + 1]:\n",
    "                idx += 1\n",
    "            traverse(idx + 1)\n",
    "\n",
    "        traverse(0)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        nums.sort()\n",
    "        res, length, tmp = [], len(nums), []\n",
    "        def traverse(idx: int):\n",
    "            if idx == length:\n",
    "                res.append(tmp.copy())\n",
    "                return\n",
    "\n",
    "            tmp.append(nums[idx])\n",
    "            # if tmp not in res:\n",
    "            traverse(idx + 1)\n",
    "            tmp.pop()\n",
    "            # if tmp not in res:\n",
    "            while idx + 1 < length and nums[idx] == nums[idx + 1]:\n",
    "                idx += 1\n",
    "            traverse(idx + 1)\n",
    "\n",
    "        traverse(0)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = set()\n",
    "        def deepin(i, parts):\n",
    "            if i>=len(nums):\n",
    "                res.add(parts)\n",
    "                return\n",
    "            deepin(i+1, parts)\n",
    "            deepin(i+1, parts+str(nums[i])+',')\n",
    "        deepin(0, \"\")\n",
    "\n",
    "        res = [x.split(\",\") for x in list(res)]\n",
    "        res = [list(filter(lambda x: x!=\"\", x)) for x in res]\n",
    "        res = sorted([sorted([int(y) for y in x]) for x in res])\n",
    "\n",
    "        res_ = []\n",
    "        i = 0\n",
    "        while i<len(res):\n",
    "            while i+1<len(res) and res[i+1] == res[i]:\n",
    "                i += 1\n",
    "            res_.append(res[i])\n",
    "            i += 1\n",
    "        return res_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        from collections import defaultdict\n",
    "        # nums = [4,4,4,1,4]\n",
    "        ans = []\n",
    "        ans_statistic = []\n",
    "        def statistic(n):\n",
    "            tmp = defaultdict(int)\n",
    "            for i in n:\n",
    "                tmp[i] += 1\n",
    "            return tmp\n",
    "\n",
    "        def search(i,tmp):\n",
    "            tmp_s = statistic(tmp)\n",
    "            if (tmp not in ans) and (tmp_s not in ans_statistic):\n",
    "                ans.append(tmp)\n",
    "                ans_statistic.append(tmp_s)\n",
    "\n",
    "            for j in range(i,len(nums)):\n",
    "                search(j+1,tmp+[nums[j]])\n",
    "            return\n",
    "        \n",
    "        search(0,[])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        nums.sort()\n",
    "        def dfs(start, path):\n",
    "            res.append(path[:])\n",
    "            for i in range(start, len(nums)):\n",
    "                if i > start and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                dfs(i+1, path)\n",
    "                path.pop()\n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        used = [0]*n\n",
    "        def backTracking(nums,res,path,startIndex,used):\n",
    "            res.append(path[:])\n",
    "            for i in range(startIndex,n):\n",
    "                if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = 1\n",
    "                backTracking(nums,res,path,i+1,used)\n",
    "                used[i] = 0\n",
    "                path.pop()\n",
    "        backTracking(nums,res,[],0,used)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        tmp = []\n",
    "        nums = sorted(nums)\n",
    "        def back_track(index):\n",
    "            temp = tmp.copy()\n",
    "            ans.append(temp)\n",
    "            if index == len(nums):\n",
    "                return \n",
    "            for i in range(index, len(nums)):\n",
    "                if i > index and nums[i] == nums[i-1]:\n",
    "                    continue\n",
    "                tmp.append(nums[i])\n",
    "                back_track(i + 1)\n",
    "                tmp.pop()\n",
    "        back_track(0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
